// 题目描述
// 1011. 在 D 天内送达包裹的能力
// 提示
// 中等
// 559
// 传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
// 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
// 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
//   示例 1：
// 输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
// 输出：15
// 解释：
// 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
// 第 1 天：1, 2, 3, 4, 5
// 第 2 天：6, 7
// 第 3 天：8
// 第 4 天：9
// 第 5 天：10
//
// 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
// 示例 2：
// 输入：weights = [3,2,2,4,1,4], days = 3
// 输出：6
// 解释：
// 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
// 第 1 天：3, 2
// 第 2 天：2, 4
// 第 3 天：1, 4
// 示例 3：
// 输入：weights = [1,2,3,1,1], days = 4
// 输出：3
// 解释：
// 第 1 天：1
// 第 2 天：2
// 第 3 天：3
// 第 4 天：1, 1
//   提示：
// 1 <= days <= weights.length <= 5 * 104
// 1 <= weights[i] <= 500
// 通过次数
// 98K
// 提交次数
// 157.7K
// 通过率
// 62.1%
// https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days

/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {
  // 二分查找只能用在单调函数上
  // 这里明确了需要得到最低运载能力 target
  // 分析题目可以构造下面这个关于 运载能力 ability 的函数，运载天数
  // 运载能力为 ability 时，需要的运载天数
  const getNeedDays = ability => {
    let days = 0
    let tmp = 0
    for (const weight of weights) {
      tmp += weight
      if (tmp > ability) {
        ++days
        tmp = weight
      }
    }

    days += (tmp > 0) ? 1 : 0

    return days
  }

  // left 的初始值是最小运载能力
  // right 的初始值是最大运载能力
  let [left, right] = weights.reduce(([left, right], cur) => {
    return [Math.max(left, cur), right + cur]
  }, [0, 0])
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const needDays = getNeedDays(mid)

    // 这里需要注意的是 需要天数 和 运载能力 成反比，单调递减
    if (needDays === days) {
      right = mid - 1
    } else if (needDays > days) { // 所以这里要注意，和平时反过来了
      left = mid + 1
    } else if (needDays < days) { // 这里也要注意，和平时反过来了
      right = mid - 1
    }
  }

  // 答案一定存在，所以不需要判定边界
  return left
}


console.log(
  shipWithinDays(
    [1, 2, 3, 1, 1],
    4
  )
)
